#include <stdio.h>
#include <limits.h>
#include <malloc.h>

/* Program to check if an input binary tree is BST or not */

typedef struct node Node;

struct node{
	int data;
	Node *left, *right;
};

Node *newTreeNode(int);
int checkBST(Node *);
int checkBSTMain(Node *, int, int);
int checkBSTMain2(Node *head, int low, int high);
int main(){
	Node *head;
	/*
			1234567
					4
			2				5
		1		3		6		7
	*/
	head = newTreeNode(4);
	head->left = newTreeNode(2);
	head->left->left = newTreeNode(1);
	head->left->right = newTreeNode(3);
	head->right = newTreeNode(6);
	head->right->left = newTreeNode(5);
	head->right->right = newTreeNode(7);
	
	printf("\nChecking BST: %d %s", checkBST(head), checkBST(head)?"True":"False");
	
	
	printf("\n--Checking Binary Tree for BST properties \n");
	return 0;
}

Node *newTreeNode(int data){
	Node *newtreenode = (Node *)malloc(sizeof(Node));
	newtreenode->data = data;
	newtreenode->left = NULL;
	newtreenode->right = NULL;
	return newtreenode;
}

int checkBST(Node *head){
	return checkBSTMain(head, INT_MIN, INT_MAX);
}

int checkBSTMain(Node *head, int low, int high){
	return ((head)?(head->data >= low && head->data <= high && checkBSTMain(head->left, low, head->data) && checkBSTMain(head->right, head->data, high)):1);
}
